package me.chan.graph;

import me.chan.queue.Queue;
import me.chan.std.StdOut;

/**
 * Created by JanGin on 2020/4/26.
 */
public class GraphSearcher {

    private boolean[] visited;
    private final int s;    //遍历起点
    private Queue<Integer> queue;

    public GraphSearcher(Graph graph, int s) {
        visited = new boolean[graph.getVetex()];
        this.s = s;
    }

    public void dfs(Graph graph, int vertex) {

        visited[vertex] = true;
        StdOut.printf("%d\t", vertex);
        for (int  adj : graph.adj(vertex)) {
            if (!visited[adj])
                dfs(graph, adj);
        }
    }

    public void bfs(Graph graph, int vertex) {

        if (null == queue)
            queue = new Queue<>();

        visited[vertex] = true;
        StdOut.printf("%d\t", vertex);
        queue.enqueue(vertex);
        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            for (int w : graph.adj(v)) {
                if (!visited[w]) {
                    visited[w] = true;
                    queue.enqueue(w);
                }
            }
        }
    }

    /**
     * 查看某个节点是否已被访问过
     * @param vertex
     * @return
     */
    public boolean visited(int vertex) {
        return visited[vertex];
    }

}
